package dp;

public class _11_494_目标和_滚动数组 {
	// 本题不够理解！
	// 求组合总数的递推公式：dp[j] += dp[j-nums[i]];
    public static int findTargetSumWays(int[] nums, int target) {
    	int sum = 0;
    	for(int i = 0; i < nums.length; i++) {
    		sum += nums[i];
    	}
    	if((target + sum) % 2 == 1) {
    		return 0;
    	}
    	// target是负数 且 其正数比sum大，没有方案
    	if(target < 0 && sum < -target) {
    		return 0;
    	}
    	// 正数的和需要是leftSum，另一半的则是负数
    	int leftSum = (target + sum) / 2;
    	// 确保正数和是正的
    	if(leftSum < 0) leftSum = -leftSum;

    	int dp[] = new int[leftSum + 1];
    	dp[0] = 1;
    	for(int i = 0; i < nums.length; i++) {
    		for(int j = leftSum; j >= nums[i]; j--) {
    			dp[j] += dp[j-nums[i]];
    		}
    	}
    	
    	return dp[leftSum];
    }
    
    public static void main(String[] args) {
    	int[] nums = {1,2,3,4,5};
    	System.out.println(findTargetSumWays(nums,3));
	}
}
